package com.yzy.leetcode;

import com.yzy.common.TreeNode;

import java.util.*;

/**
 * Description:
 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

 调用 next() 将返回二叉搜索树中的下一个最小的数。

  

 示例：



 BSTIterator iterator = new BSTIterator(root);
 iterator.next();    // 返回 3
 iterator.next();    // 返回 7
 iterator.hasNext(); // 返回 true
 iterator.next();    // 返回 9
 iterator.hasNext(); // 返回 true
 iterator.next();    // 返回 15
 iterator.hasNext(); // 返回 true
 iterator.next();    // 返回 20
 iterator.hasNext(); // 返回 false
  

 提示：

 next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

 * Date: 2019-02-27
 *
 * @author youzhiyong
 */
public class LeetCode173 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);

        root.right = new TreeNode(7);

        BSTIterator obj = new BSTIterator(root);
        int param_1 = obj.next();
        boolean param_2 = obj.hasNext();
    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    static class BSTIterator {

        private List<Integer> list;
        private int size;
        private int index;

        public BSTIterator(TreeNode root) {
            this.list = new ArrayList<>();
            this.parse(root);
            this.index = 0;
            this.size = list.size();
        }

        private void parse(TreeNode root) {
            if (root == null) return;
            if (root.left != null) parse(root.left);
            this.list.add(root.val);
            if (root.right != null) parse(root.right);
        }

        /** @return the next smallest number */
        public int next() {
            return list.get(index++);
        }

        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return index < size;
        }
    }

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

}
